package com.example.algorithm.tree;

import java.util.ArrayDeque;

/**
 * @author : zhy
 * @since : 2022/7/30
 * 翻转二叉树
 */
public class ReverseTree {


    /**
     * 深度遍历法
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if(root==null)
        {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        swapChild(root);
        return root;
    }

    private void swapChild(TreeNode root) {
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
    }



    /***********************************广度遍历法*********************/

    public TreeNode invertTree1(TreeNode root)
    {
        if(root==null)
        {
            return null;
        }
        //ArrayDeque可以当队列或者栈来使用
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty())
        {
            int len=deque.size();
            while(len>0)
            {
                TreeNode pop = deque.pop();
                swapNode(pop);
                if(pop.left!=null)
                {
                    deque.offer(pop.left);
                }
                if(pop.right!=null)
                {
                    deque.offer(pop.right);
                }
            }
        }
        return root;
    }

    private void swapNode(TreeNode root) {
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
    }
}
